#include "heap.h"

/**
 * @brief 获取父节点索引
 * @param i 当前节点索引
 * @return 父节点索引
 */
static size_t heap_parent(size_t i) 
{
    return (i + 1) / 2 - 1;
}

/**
 * @brief 获取左子节点索引
 * @param i 当前节点索引
 * @return 左子节点索引
 */
static size_t heap_left(size_t i) 
{
    return i * 2 + 1;
}

/**
 * @brief 获取右子节点索引
 * @param i 当前节点索引
 * @return 右子节点索引
 */
static size_t heap_right(size_t i) 
{
    return i * 2 + 2;
}

/**
 * @brief 向上调整堆，维护最小堆性质
 * @param a 堆数组
 * @param pos 要调整的位置
 */
static void heap_up(HeapItem *a, size_t pos) 
{
    HeapItem t = a[pos];
    while (pos > 0 && a[heap_parent(pos)].val > t.val) 
    {
        // 与父节点交换
        a[pos] = a[heap_parent(pos)];
        *a[pos].ref = pos;
        pos = heap_parent(pos);
    }
    a[pos] = t;
    *a[pos].ref = pos;
}

/**
 * @brief 向下调整堆，维护最小堆性质
 * @param a 堆数组
 * @param pos 要调整的位置
 * @param len 堆的大小
 */
static void heap_down(HeapItem *a, size_t pos, size_t len) 
{
    HeapItem t = a[pos];
    while (true) {
        // 在父节点和其子节点中找到最小的
        size_t l = heap_left(pos);
        size_t r = heap_right(pos);
        size_t min_pos = pos;
        uint64_t min_val = t.val;
        
        if (l < len && a[l].val < min_val) 
        {
            min_pos = l;
            min_val = a[l].val;
        }
        if (r < len && a[r].val < min_val) 
        {
            min_pos = r;
        }
        if (min_pos == pos) {
            break;
        }
        
        // 与子节点交换
        a[pos] = a[min_pos];
        *a[pos].ref = pos;
        pos = min_pos;
    }
    a[pos] = t;
    *a[pos].ref = pos;
}

void heap_update(HeapItem *a, size_t pos, size_t len) 
{
    if (pos > 0 && a[heap_parent(pos)].val > a[pos].val) 
    {
        heap_up(a, pos);
    } 
    else 
    {
        heap_down(a, pos, len);
    }
} 